\documentclass[12pt,a4]{article}



\input{preamble}



\setcounter{section}{1}


\begin{itemize}
 \item Homework assignment published on Monday, 2018-03-05.
 \item Work on it and submit a first solution or questions by Sunday, 2018-03-11, 12:00 by
 email to me and the TAs.
 \item You will receive feedback by Wednesday, 2018-03-14.
 \item Submit your final solution by Sunday, 2018-03-18 to me and the TAs.
\end{itemize}



\section{Partial Orderings}



\subsection{Equivalence Relations as a Partial Ordering}

An equivalence relation $R \subseteq V \times V$ is basically the same as a partition
of $V$. A {\em partition} of $V$ is a set $\{V_1,\dots,V_k\}$ where
(1) $V_1 \cup \dots \cup V_k = V$ and (2) the $V_i$ are pairwise disjoint,
i.e., $V_i \cap V_j  = \emptyset$ for $1 \leq i < j \leq k$. For example,
$\{ \{1\}, \{2,3\}, \{4\} \}$ is a partition of $\{1,2,3,4\}$ but
$\{ \{1\}, \{2,3\}, \{1,4\}\}$ is not.



\begin{exercise}
  Let $E_4$ be the set of all equivalence relations on $\{1,2,3,4\}$. Note that
  $E_4$ is ordered by set inclusion, i.e.,
  \begin{align*}
     (E_4, \{ (R_1,R_2) \in E_4 \times E_4 \ | \ R_1 \subseteq R_2 \} )
  \end{align*}
  is a partial ordering.
  \begin{enumerate}
    \item Draw the Hasse diagram of this partial ordering in a  nice way.

    \includegraphics[width = 0.8 \textwidth]{hasse.png}
    \item What is the size of the largest chain?
    
    4.
    \item What is the size of the largest antichain? 
    
    7.
  \end{enumerate}
  \end{exercise}


\subsection{Chains and Antichains}

Define the partially ordered set $(\nn, \leq)$ as follows:
$x \leq y$ if $x_i \leq y_i$ for all $1 \leq i \leq n$. For example,
$(2,5,4) \leq (2,6,6)$ but $(2,5,4) \not \leq (3,1,1)$.

\begin{exercise}
  Consider the infinite partially ordered set $(\nn, \leq)$.
  \begin{enumerate}
  \item
    Which elements are minimal? Which are maximal?
    \par The minimal element is $(0,0,0,\cdots,0)$.(There are $n 0$s in the element.)
    \par No element is maximal.
  \item Is there a minimum? A maximum?
    \par The minimum element is $(0,0,0,\cdots,0)$.(There are $n 0$s in the element.)
    \par No element is maximum.
  \item Does it have an infinite chain?
    \par Yes. We consider an chain like this:
    \begin{center}
    $\{(1,1,1,\cdots,1),(2,2,2,\cdots,2),
    (3,3,3,\cdots,3),\cdots,(k,k,\cdots,k)\}$
    \end{center}
    \par For every element in the chain, there are $n$ elements in it.
  \item Does it have arbitrarily large antichains? That is, can you find an
  antichain $A$ of size $|A| = k$ for every $k \in \N$?
    \par Yes. We consider an antichain like this:
    \begin{center}
    $\{(0,k-1,0,\cdots,0),(1,k-2,0,\cdots,0),
    (2,k-3,0,\cdots,0),\cdots,(k-1,0,0,\cdots,0)\}$
    \end{center}
    \par For every element in the antichain, the first element in each element of the antichain is increasing from $0$ to $k-1$, and similarly, the second element in each element of the antichain is decreasing from $k-1$ to $0$. As for the other elements, it can be any natural numbers and in the example, we use $0$ to replace them because it is an easy way to express this.

\end{enumerate}
\end{exercise}

\begin{exerciseD}
  Does every infinite subset $S \subseteq \nn$ contain
  an infinite chain?
\end{exerciseD}

\begin{proof}
\par
Base case $n=1$: Apparently, every two elements in set $N_0^0$ is comparable since there is only one dimension. If there exists an infinite subset $S \subseteq \N_0^0$, the subset $S$ itself is an infinite chain.
So, the theorem holds when $n=1$. \\
Inductive hypothesis: \\
\indent Suppose the theorem holds for all values of $n$ up to some $k$, $k \geq 1$.\\
Inductive step: \\
\indent Let $n=k+1$. Let $S$ be an infinite subset of $\N_0^{k+1}$, note
\begin{equation}
\begin{aligned}
S_1 &= \{ (a_1, a_2, ..., a_k) &| (a_1, a_2, ..., a_k, a_{k+1}) \in S \}\\
S_2 &= \{ a_{k+1} &| (a_1, a_2, ..., a_k, a_{k+1}) \in S \}
\end{aligned}
\end{equation}
\indent Since $S$ is infinite, at least one of $S_1, S_2$ is infinite. \\
\indent Suppose $S_1$ is infinite, according to inductive hypothesis, there is an infinite chain $C_k$ for $S_1 \subseteq \N_0^k$.
\begin{equation}
\begin{aligned}
C_k &= (A_1, A_2, \cdots), A_1 \leq A_2 \leq \cdots \\
A_i &= (a_{i1}, a_{i2}, \cdots, a_{ik})
\end{aligned}
\end{equation}
\indent Now we construct an infinite chain $C_{k+1}$ for $S \subseteq \N_0^{k+1}$.  Take one $b$ from $S_2$, we append every $A_i$ with the same constant $b$ to get $B_i$. The last number of $B_i$ is same, so $B_i$ can still form a chain $C_{k+1}$.
\begin{equation}
\begin{aligned}
B_i &= (a_{i1}, a_{i2}, \cdots, a_{ik}, b)\\
C_{k+1} &= (B_1, B_2, \cdots), B_1 \leq B_2 \leq \cdots
\end{aligned}
\end{equation}
\indent So $C_{k+1}$ is an infinite chain for $S \subseteq \N_0^{k+1}$.\\
\indent Now suppose $S_1$ is finite and $S_2$ is infinite. Notice that $S_2$ itself is an infinite chain. We take $(a_1, a_2, ..., a_k) \in S_1$ and we can construct an infinite chain for $S \subseteq \N_0^{k+1}$ in a similar way.

So, the theorem holds for $n=k+1$.
By the principle of mathematical induction, the theorem holds for all $n \in \mathbb{N}$.
\end{proof}

\begin{exercise}
  Show that $(\nn,\leq)$ has no infinite antichain. \textbf{Hint.} Use
  the previous exercise.
\end{exercise}
\begin{proof}
We proof it by contradiction. Suppose there is an infinite antichain which is also a subset of $\nn$. But from Exercise 2.3, it is clear to us that every infinite subset $S \subseteq \nn$ contain an infinite chain. So there is a contradiction. Consequently, $(\nn,\leq)$ has no infinite antichain.
\end{proof}



Consider the induced ordering on $\{0,1\}^n$. That is, for $x,y\in \{0,1\}^n$
we have $x \leq y$ if $x_i \leq y_i$ for every coordinate $i \in [n]$.

\begin{exercise}
 Draw the Hasse diagrams of $(\{0,1\}^n, \leq)$ for $n=2,3$.

\includegraphics[width = 0.8 \textwidth]{23.jpg}
\end{exercise}

\begin{exercise}
  Determine the maximum, minimum, maximal, and minimal elements of
  $\{0,1\}^n$.
\end{exercise}
\begin{center}
Maximum element:$(1,1,1,\cdots,1)$
\par Maximal element:$(1,1,1,\cdots,1)$
\par Minimum element:$(0,0,0,\cdots,0)$
\par Minimal element:$(0,0,0,\cdots,0)$
\end{center}
\begin{exercise}
  What is the longest chain of $\{0,1\}^n$?
  \par One of the examples is as follows:
  \begin{center}
  $\{(0,0,0,\cdots,0),(1,0,0,\cdots,0),
  (1,1,0,\cdots,0),\cdots,(1,1,1,\cdots,1)\}$
  \end{center}
\end{exercise}


\begin{exerciseDD}
  What is the largest antichain of $\{0,1\}^n$?
\end{exerciseDD}


The largest antichain of $\{0,1\}^n$ is the middle level of the Hasse diagram, and the number of elements in the largest antichain is $n \choose \floor{\frac{n}{2}}$.
\begin{proof}
Note the $i$th level of the Hasse diagram of $\{0,1\}^n$ as $L_i$. 
\begin{equation}
L_i=\{S|S\in \{0,1\}^n , number~ of~ 1s~ in~ S~ is~ i\}
\end{equation}
Note a sequence $S \in \{0,1\}^n$ as
\begin{equation}
S = \{a_1, a_2, \cdots, a_n\}.
\end{equation}
 
\par We will first prove that given an antichain $A$ and two adjacent levels $L_i$ and $L_{i+1}$ in the Hasse diagram ($0\leq i < \floor{\frac{n}{2}}$), we can get an new antichain $A'$ having the following properties:
\begin{itemize} 
\item $L_i \cap A' = \emptyset$.
\item $|L_{i+1} \cap A'| = |L_i \cap A| + |L_{i+1} \cap A|$.
\item $L_j \cap A' = L_j \cap A, for~ j \not = i~, i+1$.
\end{itemize}
That means we can move antichain elements in level $L_i$ to level $L_{i+1}$ without changing the rest antichain elements.
\\
We can select a subset $D$ from $L_i$ and subset $T$ from $L_{i+1}$ so that
\begin{equation}
\begin{aligned}
D&=L_i \cap A \\
T&=\{S|S \in L_{i+1},~ S ~ is ~ a ~ direct ~ succession ~ of ~ D \}
\end{aligned}
\end{equation}

Following is an example of $D$ and $T$. Elements in antichain $A$ is shown as blue boxes. $D=\{\{1000\},\{0100\}\}$. $T$ is shown as yellow boxes.
\newpage
\begin{figure}[hpbt]
\begin{center}
\includegraphics[width = 0.6 \textwidth]{pic2_8.png}
\end{center}
\end{figure}

First we will prove that if we delete $D$ from antichain $A$ and then add $T$ to get $A'$. $A'$ is still an antichain after moving operation.
\par
Suppose that after this operation, there are new relations between elements in $T$ and origin antichain $x$ in level $L_y$, shown as the dot line in the picture. Since $T$ is direct succession of $D$, there must be element in $D$ that have relation with $x$, which means there are two comparable elements in the origin antichain $A$. It is against the definition of antichain, so $A'$ is still an antichain after moving operation.

\par Then we will prove after the moving operation, 
\begin{equation}
|A| < |A'|
\end{equation}

\par Observe that the sum of in-degree of $T$ is at least the sum of out-degree of $D$, because there are in-degrees provided by non-antichains nodes in level $L_i$.
\begin{equation}
indegree(T) \geq outdegree(D)
\end{equation} 

We can calculate in-degree and out-degree of an element $S_i \in L_i$. Out-degree of $S_{i}$ is $n-i$ since out-degree equals to the number of 0s in $S_i$. In-degree of $S_{i}$ is $i$ since in-degree equals to the number of 1s in $S_i$.
%We can calculate in-degree and out-degree of an element $S_i \in L_i$. Out-degree of $S_{i}$ is $n-i$ since out-degree equals to the number of 0s in $S_i$. In-degree of $S_i$ is the sum of out-degree provided by previous level $L_{i-1}$ divided by the number of elements in $L_i$.
\begin{equation}
\begin{aligned}
outdegree(S_{i}) &= n-i\\
indegree(S_{i}) &= i
\end{aligned}
\end{equation}

Rewrite inequality (7) as
\begin{equation}
\begin{aligned}
|T| \cdot indegree(S_{i+1}) &\geq |D| \cdot outdegree(S_i)\\
\frac{|T|}{|D|} &\geq \frac{outdegree(S_i)}{indegree(S_{i+1})}\\
\frac{|T|}{|D|} &\geq \frac{n-i}{i+1} = \frac{{n \choose {i+1}}}{{n \choose i}}
\end{aligned} 
\end{equation}
If $0 \leq i \leq \floor{\frac{n}{2}}-1$,
\begin{equation}
\begin{aligned}
\frac{|T|}{|D|} \geq \frac{{n \choose {i+1}}}{{n \choose i}} > 1
\end{aligned} 
\end{equation}

Therefore we prove that there are enough "space" in level $L_{i+1}$ for moving antichain in level $L_i$ to $L_{i+1}$.

\par
So far we have proved that it is feasible to move antichain elements from level $L_i$ to $L_{i+1}$ and get a larger antichain if $0 \leq i \leq \floor{\frac{n}{2}}-1$.
\par
Notice that given an antichain configuration, we can always ajust the antichain to the middle level $L_{\floor{\frac{n}{2}}}$ by adjusting two adjacent levels. So the size of largest antichain must be equal or less than the size of middle level $L_{\floor{\frac{n}{2}}}$. 
\par 
However, the middle level itself is an antichain. So the largest antichain is the middle level $L_{\floor{\frac{n}{2}}}$.

\end{proof}


\subsection{Infinite Sets}

In the lecture (and the lecture notes) we have showed that $\N \times \N \cong \N$, i.e.,
there is a bijection $f: \N \times \N \rightarrow \N$. From this, and by induction, it follows
quite easily that $\N^k \cong \N$ for every $k$.

\begin{exercise}
  Consider $\mathbb{N}^*$, the set of all finite sequences of natural numbers, that is, $\mathbb{N}^{*}=\{\epsilon\}\cup\mathbb{N}\cup\mathbb{N}^2\cup\mathbb{N}^3\ldots$. Here,$\epsilon$ is the empty sequence. Show that $\mathbb{N}\cong\mathbb{N}^*$ by defining a bijection $\mathbb{N}\to\mathbb{N}^*$.
\end{exercise}

\begin{proof}
First we can proof $\{0,1\}^*\cong\mathbb{N}$:\\
Formally, we can define a function:
\begin{align}
\nonumber f_1:\{0,1\}^*\to\mathbb{N},&\forall a=(a_1^{(n)},a_2^{(n)},a_3^{(n)},\ldots,a_n^{(n)}) \in \{0,1\}^{*},a_i^{(n)}=0 or 1,i=1,2,\ldots,n \\
\nonumber &\to 10^n+\sum_{i=1}^n10^{i-1}a_i^{(n)}
\end{align}
\[\]
For example:$f_1(001010)=1001010_{10}$.\\Then we can define another function:
\[f_2:\mathbb{N}\to\{0,1\}^*,decimal \quad number \to binary\]
For example:$f_2(16)=10000$.So we get the conclusion:\\
\[\{0,1\}^*\cong\mathbb{N} \eqno(1)\]
Secondly, we can proof $\{0,1\}^*\cong\mathbb{N}^*$:\\
Define a function:
\[f_3:\{0,1\}^*\to\mathbb{N}^*,x \to x\]
Another function:
\begin{align}
\nonumber f_4:\mathbb{N}^*\to\{0,1\}^*,&\forall a=(a_1^{(n)},a_2^{(n)},a_3^{(n)},\ldots,a_n^{(n)}) \in \mathbb{N}^{*},a_i^{(n)} \in \mathbb{N},i=1,2,\ldots,n\\
\nonumber \to&(\underbrace{{0,0,\ldots,0}}_{a_1^{(n)}},1,\underbrace{0,0,\ldots,0}_{a_2^{(n)}},1,\ldots,1,\underbrace{0,0,\ldots,0}_{a_n^{(n)}},1)
\end{align}
For example, $f_4((2,3,1,4))=00100010100001$. So we get the conclusion:\\
\[\{0,1\}^*\cong\mathbb{N}^*\eqno(2)\]
According (1) and (2), $\mathbb{N}\cong\mathbb{N}^*$ is obvious.
\end{proof}

\begin{exercise}
   Show that $R \cong R \times R$. \textbf{Hint:} Use the fact that
   $R \cong \{0,1\}^{\N}$ and thus show that $\{0,1\}^{\N} \cong \{0,1\}^{\N} \times \{0,1\}^{\N}$.
\end{exercise}

\begin{proof}
Obvious, there exits a function:
\begin{align}
\nonumber f_1:\{0,1\}^{\mathbb{N}} \to \{0,1\}^{\mathbb{N}} \times \{0,1\}^{\mathbb{N}}, x \to (x, 0000\ldots)
\end{align}
Then, we define a function:
\begin{align}
\nonumber f_2:\{0,1\}^{\mathbb{N}} \times \{0,1\}^{\mathbb{N}} \to \{0,1\}^{\mathbb{N}}, (a_1a_2a_3\ldots, b_1b_2b_3\ldots) \to (a_1b_1a_2b_2a_3b_3\ldots)
\end{align}
Such as:\\
\begin{center}
\includegraphics[scale=0.8]{1.png} 
\end{center}
Therefore, we proof $\{0,1\}^{\mathbb{N}} \cong \{0,1\}^{\mathbb{N}} \times \{0,1\}^{\mathbb{N}}$, and then $R \cong R \times R$.
\end{proof}

\begin{exercise}
Consider $R^{\mathbb{N}}$, the set of all infinite sequences $(r_1, r_2, r_3, \ldots)$ of real numbers. Show that $R \cong R^{\mathbb{N}}$. \textbf{Hint:} Again, use the fact that $R \cong \{0,1\}^{\mathbb{N}}$.
\end{exercise}

\begin{proof}
We only need to proof that ${(\{0,1\}^{\mathbb{N}})}^{\mathbb{N}} \cong \{0,1\}^{\mathbb{N}}$.
Firstly, we can know the following function easily:
\begin{align}
f_1:\{0,1\}^{\mathbb{N}} \to {(\{0,1\}^{\mathbb{N}})}^{\mathbb{N}}, x \to (x, 00000\ldots, 00000\ldots,00000\ldots, \ldots).
\end{align}
\begin{center}
\includegraphics[scale=0.6]{2.png} 
\end{center}
Then,define a complexer function:
\begin{align}
f_2:{(\{0,1\}^{\mathbb{N}})}^{\mathbb{N}} \to \{0,1\}^{\mathbb{N}},(x_1^1x_2^1x_3^1\ldots,x_1^2x_2^2x_3^2\ldots,x_1^3x_2^3x_3^3\ldots
,\ldots) \to (x_1^1x_1^2x_2^2x_1^2x_1^3x_2^3\ldots),x_i^j=0\:or\:1
\end{align}
\begin{center}
\includegraphics[scale=0.6]{3.png} 
\end{center}
Now, we can infer ${(\{0,1\}^{\mathbb{N}})}^{\mathbb{N}} \cong \{0,1\}^{\mathbb{N}}$ is true. Thus, $R \cong R^{\mathbb{N}}$.
\end{proof}

Next, let us view $\{0,1\}^{\N}$ as a partial ordering: given two elements $\mathbf{a}, \mathbf{b} \in \{0,1\}^{\N}$,
that is, sequences $\mathbf{a} = (a_1,a_2,\dots)$ and $\mathbf{b} = (b_1,b_2,\dots)$, we define
$\mathbf{a} \leq \mathbf{b}$ if $a_i \leq b_i$ for all $i \in \N$. Clearly,
$(0,0,\dots)$ is the minimum element in this ordering and $(1,1,\dots)$ the maximum.\\

\begin{exercise}
   Give a countably infinite chain in $\{0,1\}^{\N}$. Remember that a set $A$ is countably infinite
   if $A \cong \N$.
\end{exercise}
    $$ (0, 0, 0, \dots) $$
    $$ (1, 0, 0, \dots) $$
    $$ (1, 1, 0, \dots) $$
    $$ (1, 1, 1, \dots) $$
    $$ \dots $$

    Since there are countably infinite bits in every element, we can construct countably infinite chain in $\{0,1\}^{\N}$ as showed above.

\begin{exercise}
   Find a countably infinite antichain in $\{0,1\}^{\N}$.
\end{exercise}
    $$ (1, 0, 0, \dots) $$
    $$ (0, 1, 0, \dots) $$
    $$ (0, 0, 1, \dots) $$
    $$ \dots $$

    Since there are countably infinite bits in every element, we can construct countably infinite chain in $\{0,1\}^{\N}$ as showed above.


\begin{exercise}
   Find an uncountable antichain in $\{0,1\}^{\N}$. That is, an antichain $A$ with $A \cong \R$.
\end{exercise}
    Since $\{0,1\}^{\N} \cong \R$, there is a bijection: $x \leftrightarrow \mathbf{t}$, $x \in \R, \mathbf{t} \in \{0,1\}^{\N}$. Let's consider $\mathbf{t_i}$.
    $$ \mathbf{t_i} = (a_1, a_2, \dots), a_k \in \{0,1\}, k \in \N $$
    Define $\bar{\mathbf{t_i}} = (1-a_1, 1-a_2, \dots)$.
    Then construct $\hat{\mathbf{t_i}}$ as:
    $$ \hat{\mathbf{t_i}} = (a_1, 1-a_1, a_2, 1-a_2, \dots) $$
    Consider $\hat{\mathbf{t_i}}, \hat{\mathbf{t_j}}, \forall i, j \in \N, i \neq j$.

    \textbf{Case 1:} If $\mathbf{t_i} \nleq \mathbf{t_j}$, obviously, $\hat{\mathbf{t_i}} \nleq \hat{\mathbf{t_j}}$.

    \textbf{Case 2:} If $\mathbf{t_i} \leq \mathbf{t_j}$
    
    $$\mathbf{t_i}=(a_1, a_2, \dots)\quad \bar{\mathbf{t_i}}=(1-a_1, 1-a_2, \dots)$$
    $$\mathbf{t_j} = (b_1, b_2, \dots)\quad \bar{\mathbf{t_j}} = (1-b_1, 1-b_2, \dots)$$

    According to the definition of $\mathbf{a} \leq \mathbf{b}$, we know that $a_k \leq b_k$. So, $\bar{\mathbf{t_i}} \geq \bar{\mathbf{t_j}}$.

    Compare every bit of $\hat{\mathbf{t}}$.
    $$
    \begin{array}{c|lcccr}
    \hat{\mathbf{t}} & 1 & 2 & 3 & 4 & \dots \\
    \hline
    \hat{\mathbf{t_i}} & a_1 & 1-a_1 & a_2 & 1-a_2 & \dots \\
    \hat{\mathbf{t_j}} & b_1 & 1-b_1 & b_2 & 1-b_2 & \dots \\
    \end{array}
    $$

    Since $a_k \leq b_k$, $1-a_k \geq 1-b_k$. 
    
    And since $i \neq j$, $\mathbf{t_i}, \mathbf{t_j}$ are not the same $\mathbf{t}$, which means that $\exists \eta, a_{\eta} < b_{\eta}, 1-a_{\eta} > 1-b_{\eta}$. So, $\hat{\mathbf{t_i}} \nleq \hat{\mathbf{t_j}}$.

    Therefore, $\hat{\mathbf{t_1}} \quad \hat{\mathbf{t_2}} \quad \dots$ is an uncountable antichain in $\{0,1\}^{\N}$.


\begin{exerciseDD}
   Find an uncountable chain in $\{0,1\}^{\N}$. That is, an antichain $A$ with $A \cong \R$.
\end{exerciseDD}

\begin{proof}
As we has learnt in our class, $\exists f : \mathbb{N} \leftrightarrow \mathbb{Q}$.
So we can arrange $ \mathbb{Q} $ in the sequence of $\mathbb{N}$, such as:\\
\begin{center}
\begin{tabular}{ccccccc}
$\mathbb{N}$ & 1 & 2 & 3 & 4 & 5 & $\ldots$ \\
$\mathbb{Q}$ & f(1) & f(2) & f(3) & f(4) & f(5) & $\ldots$
\end{tabular}
\end{center}
Construct a set $\mathbb{S}$,\\
\[\mathbb{S} = \{(i_1,i_2,\ldots,i_k,\ldots) \in \{0,1\}^{\mathbb{N}} | i_k=\left\{
\begin{array}{rcl}
1       &      & f(k)\le x\\
0     &      &  f(k) > x
\end{array} \right.
(x \in \mathbb{R} )\}
\]
Because between any two real number $x_1, x_2$, there must be a $q \in \mathbb{Q}$,
that obviously we can find it in the sequence of $\mathbb{Q}$, it well only be 1 in one of the sequence generated from $x_1, x_2$, so for any different x, a sequence is corresponding to it , so $g: x \rightarrow s \in \mathbb{S}$ is injective,and cardinality of $\mathbb{S}$ is larger or equal to $\mathbb{R}$ where x belongs to. What's more,
\[\\ \forall x_1 < x_2,(x_1,x_2 \in \mathbb{R}), s_1=g(x_1)=(i_1^1,i_2^1,i_3^1,\ldots), s_2 = g(x_2) = (i_1^2,i_2^2,\ldots),\]
\begin{center}
\begin{tabular}{c|c|c|c}
       &$f(k)\le x_1 $ &$ x_1 < f(k) \le x_2 $&$f(k) > x_2$\\
$i_k^1$&  1        &       0             &    0\\
$i_k^2$&  1        &       1             &    0
\end{tabular}
\end{center}
So $\forall x_1 < x_2, s_1 < s_2$, which means $\mathbb{S}$ is a chain.
So $\mathbb{S}$ is an uncountable chain of $\{0,1\}^{\mathbb{N}}$
\end{proof}

\textbf{Question:} 

\begin{enumerate}
    \item We are wondering if there is an easier or another way to solve 2.14.
    \item We are wondering how to illustrate the obvious conclusion in 2.8.
    
\end{enumerate}

\end{document}



